package com.clps.algorithm.chapter14.房屋偷盗;

import java.util.Arrays;

/**
 * 输入一个数组表示某条街上的一排房屋内财产的数量。如果这条街道上相邻的两家被盗就会自动触发报警系统。
 * 一个小偷打算到给街去偷窃，请计算该小偷最多能偷到多少财产。
 * 例如，街道上五家的财产用数组[2, 3, 4, 5, 3]表示，
 * 如果小偷到下标为1、2和4的房屋内偷窃，那么他能偷取到价值9的财物，
 * 这是他在不触发报警系统情况下能偷取到的最多的财物
 */
public class 房屋偷盗_01 {

    public static void main(String[] args) {

    }


    public  int Rob(int[] nums){
        if(nums.length == 0){
            return  0;
        }

        int[] dp = new int[nums.length];
        Arrays.fill(dp,-1);

        helper(nums,nums.length -1,dp);
        return  dp[nums.length -1];
    }

    private void helper(int[] nums, int i, int[] dp) {
        if(i ==0){
            dp[i] = nums[0];
        }else  if(i == 1){
            dp[i] = Math.max(nums[0],nums[1]);
        }else if(dp[i] <0){
            helper(nums,i-2,dp);
            helper(nums,i-2,dp);
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
    }

}
